#ifndef __ACSM__
#define __ACSM__

#include <deque>

namespace mpm
{
	struct node;

	enum 
	{
		ACSM_BAD_MALLOC = -2,
		ACSM_BAD_PARAM = -1,
		ACSM_OK,
		ACSM_PATTERN_EXIST,
		ACSM_CB_BREAK,
	};

	typedef bool (*on_hit_pattern_t)(const uint8_t * dat, size_t cb, size_t offset,void * ptnud,void * context );

	typedef unsigned char	__u8;

	typedef node *	state_t;

	struct	node
	{
		enum { NUMBYTE = 0x100 };
		node *		fail;
		void *		userdat;
		void *		__node;
		node *		__next[NUMBYTE];
		node()
		{
			memset( this,0,sizeof(node) );
		}
		inline node *& rnext( uint8_t ubc ) 
		{
			return __next[ubc];
		}
		inline node * gnext( uint8_t ubc )
		{
			return __next[ubc];
		}
		size_t num_entries()
		{
			size_t ret = 0;
			for( size_t i = 0; i < NUMBYTE; ++ i )
			{
				if( __next[i] ) ret ++;
			}
			return ret;
		}
	};

	struct __mem_mgr_t
	{
		void *	_alloc( size_t cb )
		{
			return malloc( cb );
		}
		void	_free( void * p )
		{
			free( p );
		}
	};

	template < class MEMMGR = __mem_mgr_t >
	struct acsm_t
	{
	protected:
		

	public:
		typedef node *	state_t;
		

		enum { NUMBYTE = 0x100 };

		node		_root;
		MEMMGR		_mgr;

		acsm_t( MEMMGR mmgr = MEMMGR() )
		{
			_mgr = mmgr;
		}
		~acsm_t( )
		{
			destroy();
		}

		node * root() { return &_root; };

		long search( state_t & state, const void * ptr, size_t cb, on_hit_pattern_t pcb, void * context )
		{
			if( !state ) state = root();

			const __u8 * dat = (const __u8 *)ptr;

			node * & p = state;

			for( size_t i = 0; i < cb; ++ i )
			{
				uint8_t xb = dat[i];

				while( (p->gnext(xb)==0) && (p != root() ) ) 
					p = p->fail;

				p = p->gnext(xb);
				
				if( !p )
				{
					p = root();
					continue;
				}

				node * tp = p;
				do {
					if( !tp->userdat ) 
						continue;

					if( !pcb( dat, cb, i, tp->userdat, context ) )
						return ACSM_CB_BREAK;

				} while( tp = tp->fail );
			}
			return ACSM_OK;
		}

		long insert( const void * ptr, size_t cb, void * ud, bool replace = false )
		{
			const __u8 * dat = (const __u8 *)ptr;
			node * p = root(); 
			for( size_t i = 0; i < cb; ++ i )
			{
				__u8 b = dat[i];

				if( ! p->gnext(b) ) 
					p->rnext(b) = createNode();

				if( ! p->gnext(b) ) 
					return ACSM_BAD_MALLOC;

				p = p->gnext(b);
			}

			if( !p->userdat || replace )
			{
				p->userdat = ud;
				return ACSM_OK;
			}

			if( !replace ) 
				return ACSM_PATTERN_EXIST;

			return ACSM_OK;
		}

		long complie()
		{
			std::deque< node * > _nodes;
			//////////////////////////////////////////////////////////////////////////
			root()->fail = 0;
			for( size_t ch = 0; ch < NUMBYTE; ++ ch )
			{
				node * child = root()->gnext(ch);
				if( !child ) continue;
				child->fail = root();
				_nodes.push_back( child );
			}
			//////////////////////////////////////////////////////////////////////////
			while( _nodes.size() )
			{
				node * pthis = _nodes.front(); _nodes.pop_front();
				for( size_t ch = 0; ch < NUMBYTE; ++ ch )
				{
					// each children
					// char = ch 
					node * child = pthis->gnext(ch);
					if( !child ) continue;

					// default failp is root
					child->fail = root();

					// get parent's fail-pointer( must not NULL )
					node * failnode = pthis->fail;
					do
					{
						// if parent's fail-node can't accept ch, 
						// if g(fail,ch) exist, child .fail -> node(ch)
						node * target = failnode->gnext(ch);
						if( !target ) continue;

						// if 
						child->fail = target;
						break;

					} while( failnode = failnode->fail );

					//printf( "%08X -> %08X\n", child, (child->fail) );
					_nodes.push_back( child );
				}
			}
			return ACSM_OK;
		}

		void destroy()
		{
			for( uint32_t ch = 0; ch < NUMBYTE; ++ ch )
			{
				node * & child = root()->rnext(ch);
				if( !child ) continue;
				__destroy_node(child);
				child = 0;
			}
		}

	protected:

		node * createNode()
		{
			size_t cb = sizeof(node);
			node * p = (node *)_mgr._alloc(cb);
			memset( p, 0, cb );
			new (p) node();
			return p;
		}

		void __destroy_node( node * p )
		{
			for( uint32_t ch = 0; ch < NUMBYTE; ++ ch )
			{
				node * & child = p->rnext(ch);
				if( !child ) continue;
				__destroy_node(child);
				child = 0;
			}
			_mgr._free(p);
		}
	};

	//////////////////////////////////////////////////////////////////////////

	struct acsm2_t
	{
		typedef std::vector<uint8_t> buffer_t;

		const uint8_t *	_base;
		size_t			_bytes;

		acsm2_t() : _base(0), _bytes(0){}

		struct	node2;

		typedef node2 *	state_t;

		union next_t
		{
			size_t	offset;
			node2 * node2p;
			node *	nodep;
		};

#pragma pack(1)
		struct bent
		{
			uint8_t bt;
			next_t	nxt;
		};


		struct	node2
		{
			node2*	fail;
			void *	userdat;
			uint8_t	num;

			bent *	entries()
			{
				return (bent *)(this+1);
			}

			bent& rentry( size_t i )
			{
				return entries()[i];
			};
			bent* gentry( size_t i )
			{
				return entries()+i;
			}

			static int compare_bent( const void * left, const void * right )
			{
				const bent * _left = (const bent *)left;
				const bent * _right = (const bent *)right;
				return (int)(_left->bt) - (int)(_right->bt);
			}

			inline node2 * gnext( uint8_t ubc ) 
			{
				bent ent = { ubc, 0 };
				bent * phit = (bent *)bsearch( &ent, entries(), num, sizeof(bent), compare_bent );
				if( !phit ) return 0;
				return phit->nxt.node2p;
			}
			//inline bool rnext( next_t * & r, uint8_t ubc )
			//{
			//	bent ent = { ubc, 0 };
			//	bent * phit = bsearch( &ent, entries(), num, sizeof(bent), compare_bent );
			//	if( !phit ) return false;
			//	r = phit->nxt;
			//	return true;
			//}
		};

#pragma pack()

		enum { NUMBYTE = 0x100 };

		node2 * convertNode( node * p )
		{
			size_t cent = p->num_entries();
			
			node2 * p2 = createNode2(cent);
			if( !p2 ) return 0;
			
			p2->fail = (p->fail)?(node2*)(p->fail->__node):0;
			p2->userdat = p->userdat;
			p->__node = p2;
		
			size_t ient = 0;
			for( size_t i = 0; i < NUMBYTE; ++ i )
			{
				if( ! p->gnext(i) ) continue;
				p2->rentry(ient).bt = i;
				p2->rentry(ient).nxt.nodep = p->gnext(i);
				++ient;
			}
			p2->num = ient;
			return p2;
		}

		node2 * createNode2( size_t cent )
		{
			size_t cb = sizeof(node2) + sizeof(bent)*cent;
			node2 * p = (node2 *)malloc(cb);
			memset( p, 0, cb );
			new (p) node2;
			return p;
		}

		node2 *	_root;

		long convertFrom( node * rootp )
		{
			std::deque< node * > _nodes;
			std::vector< node2* > _node2s;
			_nodes.push_back( rootp );
			while( _nodes.size() )
			{
				node * pthis = _nodes.front(); _nodes.pop_front();
				//////////////////////////////////////////////////////////////////////////
				node2 * node2p = convertNode(pthis);
				if( !node2p ) return -1;
				_node2s.push_back(node2p);
				for( size_t ch = 0; ch < NUMBYTE; ++ ch )
				{
					node * child = pthis->gnext(ch);
					if( !child ) continue;
					_nodes.push_back( child );
				}
			}
			for( size_t i = 0; i < _node2s.size(); ++ i )
			{
				node2* pn2 = _node2s[i];
				for( size_t d = 0; d < pn2->num; ++ d )
				{
					pn2->rentry(d).nxt.node2p = (node2*)
						pn2->rentry(d).nxt.nodep->__node;
				}
			}
			_root = (node2*)rootp->__node;
			return 0;
		}

		node2 * root()
		{
			return _root;
		}

		long search( node2* & state, const void * ptr, size_t cb, on_hit_pattern_t pcb, void * context )
		{
			if( !state ) state = root();

			const __u8 * dat = (const __u8 *)ptr;

			node2 * & p = state;

			for( size_t i = 0; i < cb; ++ i )
			{
				uint8_t xb = dat[i];
				
				node2 * nxt = p->gnext(xb);
				while( (nxt==0) && (p != root() ) )
				{
					p = p->fail;
					nxt = p->gnext(xb);
				}

				p = p->gnext(xb);

				if( !p )
				{
					p = root();
					continue;
				}

				node2 * tp = p;
				do {
					if( !tp->userdat ) 
						continue;

					if( !pcb( dat, cb, i, tp->userdat, context ) )
						return ACSM_CB_BREAK;

				} while( tp = tp->fail );
			}
			return ACSM_OK;
		}

	};

};

#endif